/// @tags: solve
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>

using namespace std;

namespace BlueQuantum {

int const N = 5e4 + 5, mod = 1e4 + 7;

int n, m, mx;
int a[N], sum[N], f[N], s[N], lim[N];

inline bool check(int x) {
  int tot = 0, len = 0;
  for (int i = 1; i <= n; ++i) {
    len + a[i] > x ? (tot++, len = a[i]) : len += a[i];
    if (tot > m) return false;
  }
  return true;
}

inline int add(int x, int y) {
  if ((x += y) >= mod) x -= mod;
  return x;
}

inline int dec(int x, int y) {
  if ((x -= y) < 0) x += mod;
  return x;
}

inline int solve(int x) {
  int k = 0;
  for (int i = 1; i <= n; ++i)
    for (; k < i; ++k)
      if (sum[i] - sum[k] <= x) {
        lim[i] = k;
        break;
      }
  for (int i = 1; i <= n; ++i) {
    if (sum[i] <= x) f[i] = 1;
    s[i] = add(s[i - 1], f[i]);
  }
  int res = f[n];
  for (int i = 2; i <= m + 1; ++i) {
    for (int j = 1; j <= n; ++j) {
      f[j] = s[j - 1];
      if (lim[j] - 1 >= 0) f[j] = dec(f[j], s[lim[j] - 1]);
    }
    for (int j = 1; j <= n; ++j) s[j] = add(s[j - 1], f[j]);
    res = add(res, f[n]);
  }
  return res;
}

inline int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; ++i)
    cin >> a[i], sum[i] = sum[i - 1] + a[i], mx = max(mx, a[i]);
  int l = mx, r = sum[n], mid;
  while (l < r) {
    mid = (l + r) >> 1;
    check(mid) ? r = mid : l = mid + 1;
  }
  cout << l << ' ' << solve(l);
  return 0;
}

}  // namespace BlueQuantum

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("P2511 [HAOI2008] 木棍分割.in", "r", stdin);
  freopen("P2511 [HAOI2008] 木棍分割.out", "w", stdout);
#endif
#endif

  ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  return BlueQuantum::main();
}
